/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-12-02
 * Time: 13:34
 */
public class test4 {
    /*
    NewCoder BM4 合并两个排序的链表
    输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
     */

    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        if(pHead1==null){
            return pHead2;
        }
        if(pHead2==null){
            return pHead1;
        }
        ListNode newHead =new ListNode(-1);
        ListNode cur = newHead;
        while(pHead1!=null && pHead2!=null){
            if(pHead1.val<pHead2.val){
                cur.next = pHead1;
                pHead1 = pHead1.next;
            }else{
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            cur = cur.next;
        }
        if(pHead1==null){
            cur.next = pHead2;
        }
        if(pHead2==null){
            cur.next = pHead1;
        }
        return newHead.next;
    }


    public class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }
}
